package leetcode_400;

import java.util.Random;

/**
 *@author 周杨
 *RandomPickIndex_398 传入一个值 随机输出这个值在数组里的索引
 *describe:每次只保留这个上一个满足条件的值 AC 97%
 *2018年7月16日 上午10:23:38
 */
public class RandomPickIndex_398 {
	 int[] nums;
	 Random rand;
	 public RandomPickIndex_398(int[] nums) {
		 this.nums = nums;
	     this.rand = new Random(); 
	 }
	 
	 /**
	 * describe:每次只保留上一次的数 这样叠加的几率就相等了
	 * 2018年7月16日 上午10:23:18
	 */
	public int pick(int target) {
	        int total = 0;
	        int res = -1;
	        for (int i = 0; i < nums.length; i++) {
	            if (nums[i] == target) {
	                // randomly select an int from 0 to the nums of target. If x equals 0, set the res as the current index. The probability is always 1/nums for the latest appeared number. For example, 1 for 1st num, 1/2 for 2nd num, 1/3 for 3nd num (1/2 * 2/3 for each of the first 2 nums).
	                int x = rand.nextInt(++total); 
	                res = x == 0 ? i : res;
	            }
	        }
	        return res;
	}
}
